package com.mlh.dp.old;

// 题目：
// 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
// 注意 这个数列必须是 严格 递增的。
// 举例：
// 输入: [1,3,5,4,7]
// 输出: 2
// 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

public class FindNumberOfLIS {

    public static void main(String[] args) {
        int[] nums={1,2,4,3,5,4,7,2};
        method1(nums);
    }

    public static int method1(int[]nums){
        int[] dp = new int[nums.length];
        int[] repeat=new int[nums.length];
        boolean flag = false;
        int maxLen = 1;
        int finalRes=0;

        dp[0]=1;
        repeat[0]=1;


        for (int i = 1; i < nums.length; i++) {
            int maxIndex=-1;
            int max=0;
            int res=1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if(max<=dp[j]){
                        if(max<dp[j]){
                            res=repeat[j];
                        }else{
                            res+=repeat[j];
                        }
                        maxIndex=j;
                        max=dp[j];
                    }
                    flag = true;
                }
            }

            if (flag) {
                dp[i]=dp[maxIndex]+1;
                repeat[i]=res;
                maxLen = dp[i] > maxLen ? dp[i] : maxLen;
            }else {
                dp[i] = 1;
                repeat[i]=res;
                maxLen = dp[i] > maxLen ? dp[i] : maxLen;
            }
            flag = false;
        }


        for(int i=0;i<nums.length;i++){
            System.out.print(dp[i]+" ");
           if(dp[i]==maxLen){
               finalRes+=repeat[i];
           }
        }
        return finalRes;
    }

    //leetcode答案
    public int findNumberOfLIS1(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) ans += g[i];
        }
        return ans;
    }

    //method的优化
    public static int method2(int[]nums){
        int[] dp = new int[nums.length];
        int[] repeat=new int[nums.length];
        int maxLen = 1;
        int finalRes=0;

        for (int i = 0; i < nums.length; i++) {
            repeat[i]=1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if(dp[i]<=dp[j]){
                        if(dp[i]<dp[j]){
                            repeat[i]=repeat[j];
                        }else{
                            repeat[i]+=repeat[j];
                        }
                        dp[i]=dp[j];
                    }
                }
            }
            dp[i]++;
            maxLen=dp[i]>maxLen?dp[i]:maxLen;
        }

        for(int i=0;i<nums.length;i++){
            if(dp[i]==maxLen){
                finalRes+=repeat[i];
            }
        }
        return finalRes;
    }

}
